package com.leetcode.根据数据结构分类.并查集;

/**
 * @author: xiaomi
 * @date: 2021/2/28
 * @description: 200. 岛屿数量
 * https://leetcode-cn.com/problems/number-of-islands/
 */
public class B_200_岛屿数量 {

    static B_200_岛屿数量 action;

    public static void main(String[] args) {
        action = new B_200_岛屿数量();
//        test1();
//        test2();
        test3();
    }

    public static void test1() {
        //1
        char[][] grid = new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        int res = action.numIslands(grid);
        System.out.println(res);
    }

    public static void test2() {
        //3
        char[][] grid = new char[][]{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        int res = action.numIslands(grid);
        System.out.println(res);
    }

    public static void test3() {
        //3
        char[][] grid = new char[][]{
                {'1', '0', '1', '1', '0', '1', '1'}
        };
        int res = action.numIslands(grid);
        System.out.println(res);
    }

    /**
     * 感觉这是一个求连通分量的问题
     * --
     * 由于周围都是水，可以只针对 1 进行处理
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        //行
        int m = grid.length;
        //列
        int n = grid[0].length;
        //容量
        int cap = m * n;
        InnerUnionFind unionFind = new InnerUnionFind(cap);
        int index = 0;
        int mIndex = m - 1, nIndex = n - 1;
        int zeroCount = 0;
        for (int i = 0; i < mIndex; i++) {
            int j = 0;
            for (; j < nIndex; j++) {
                if (grid[i][j] == '1') {
                    //具备合并的前提
                    if (grid[i][j + 1] == '1') {
                        if (!unionFind.isSame(index, index + 1)) {
                            unionFind.union(index, index + 1);
                        }
                    }
                    if (grid[i + 1][j] == '1') {
                        int tempIndex = index + n;
                        if (!unionFind.isSame(index, tempIndex)) {
                            unionFind.union(index, tempIndex);
                        }
                    }
                } else {
                    zeroCount++;
                }
                index++;
            }
            //此时 j= nIndex 达到末尾的元素
            //需要额外判断
            if (grid[i][j] == '1') {
                //具备合并的前提
                if (grid[i + 1][j] == '1') {
                    int tempIndex = index + n;
                    if (!unionFind.isSame(index, tempIndex)) {
                        unionFind.union(index, tempIndex);
                    }
                }
            } else {
                zeroCount++;
            }
            index++;
        }
        //还剩最后一行
        for (int j = 0; j < nIndex; j++) {
            if (grid[mIndex][j] == '1') {
                if (grid[mIndex][j + 1] == '1') {
                    if (!unionFind.isSame(index, index + 1)) {
                        unionFind.union(index, index + 1);
                    }
                }
            } else {
                zeroCount++;
            }
            index++;
        }
        if (grid[mIndex][nIndex] == '0') {
            zeroCount++;
        }
        return unionFind.count - zeroCount;
    }


    /**
     * 并查集
     */
    static class InnerUnionFind {
        int[] parents;
        /**
         * 秩
         */
        int[] rank;
        /**
         * 连通分量的个数
         */
        int count = 0;

        public InnerUnionFind(int capacity) {
            parents = new int[capacity];
            rank = new int[capacity];
            for (int i = 0; i < capacity; i++) {
                parents[i] = i;
                rank[i] = 1;
            }
            count = capacity;
        }

        public int find(int index) {
            if (parents[index] != index) {
                parents[index] = find(parents[index]);
            }
            return parents[index];
        }

        public void union(int index1, int index2) {
            int i1 = find(index1);
            int i2 = find(index2);
            if (i1 == i2) {
                return;
            }
            //每次有一个进行合并，就会减少一个连通分量
            count--;
            if (rank[i1] == rank[i2]) {
                //合并到 i2
                parents[i1] = i2;
                rank[i2]++;
            } else if (rank[i1] < rank[i2]) {
                parents[i1] = i2;
            } else {
                parents[i2] = i1;
            }
        }

        public boolean isSame(int index1, int index2) {
            return find(index1) == find(index2);
        }
    }
}
